class Solution {
public:
    string LCS(string s1, string s2) {
        if(s1.size() == 0 || s2.size() == 0)
            return "-1";

        vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1, 0));
        for(int i = 1; i <= s1.size(); i++)
        {
            for(int j = 1; j <= s2.size(); j++)
            {
                if(s1[i-1] == s2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else 
                {
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        if(dp[s1.size()][s2.size()] == 0)
            return "-1";

        int i = s1.size();
        int j = s2.size();
        string retStr;
        while(i > 0 && j > 0)
        {
            if(s1[i-1] == s2[j-1])
            {
                retStr.push_back(s1[i-1]);
                i--;
                j--;
            }
            else if(dp[i-1][j] > dp[i][j-1]) 
            {
                i--;
            }
            else if(dp[i][j-1] >= dp[i-1][j])
            {
                j--;
            }
        }

        reverse(retStr.begin(), retStr.end());

        return retStr;
    }
};

class Solution {
public:
    string LCS(string str1, string str2) {
        int m = str1.size();
        int n = str2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        int max_len = 0;
        int end_pos = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(str1[i-1] == str2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(dp[i][j] > max_len)
                    {
                        max_len = dp[i][j];
                        end_pos = i-1;
                    }
                }
                else 
                {
                    dp[i][j] = 0;
                }
            }
        }

        string retStr = str1.substr(end_pos-max_len+1, max_len);

        return retStr;
    }
};

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n,1));

        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
};

class Solution {
public:
    int minPathSum(vector<vector<int> >& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = matrix[0][0];
        for(int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + matrix[i][0];
        for(int j = 1; j < n; ++j) dp[0][j] = dp[0][j-1] + matrix[0][j];

        for(int i = 1; i < m; ++i)
        {
            for(int j = 1; j < n; ++j)
            {
                int minNum = min(dp[i-1][j], dp[i][j-1]);
                dp[i][j] = minNum + matrix[i][j];
            }
        }

        return dp[m-1][n-1];
    }
};
